/*!
 * # [104.二叉树的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/)
 *
 * @lc app=leetcode.cn id=104 lang=rust
 *
 * ## 难度
 * - Easy (76.69%)
 * - Likes:    1085
 * - Dislikes: 0
 * - Total Accepted:    586.2K
 * - Total Submissions: 763.9K
 * - Testcase Example:  '[3,9,20,null,null,15,7]'
 *
 * ## 问题描述
 *
 * 给定一个二叉树，找出其最大深度。
 *
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * ## 示例：
 *
 * 给定二叉树 [3,9,20,null,null,15,7]，
 *
 * ```text
 *    3
 *   / \
 *  9  20
 *    /  \
 *   15   7
 * ```
 *
 * 返回它的最大深度 3 。
 *
 */

use super::*;

// @lc code=start
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    /// # 二叉树的最大深度
    /// ## 解题思路
    /// - 递归
    /// `max_depth = 1 + max(max_depth(left) + max_depth(right))`
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match root {
            None => 0,
            Some(node) => {
                1 + std::cmp::max(
                    Solution::max_depth(node.borrow().right.clone()),
                    Solution::max_depth(node.borrow().left.clone()),
                )
            }
        }
    }
}
// @lc code=end
